package demo04ArrayListLinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 09 - 21
 * Time:16:04
 */

/***
 * 五、双向链表
 * 1..双向链表：
 * （1）val:
 * （2）prev : 前驱
 *  (3)next : 后继
 *
 */

//定义节点
class ListNode{
    private int val;
    private ListNode prev;
    private ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public int getVal() {
        return val;
    }

    public ListNode getPrev() {
        return prev;
    }

    public ListNode getNext() {
        return next;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public void setPrev(ListNode prev) {
        this.prev = prev;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }
}
public class myDoubleLinkedList {

    public ListNode head;//双向链表的头
    public ListNode last;//尾

    /***
     * 1.头插法——时间复杂度O(1)
     * @param data
     */
    public void addFirst(int data){
        //(0)创建节点
        ListNode node = new ListNode(data);
        //(1)链表为空时
        if(this.head == null){
            this.head = node;
            this.last = node;
        }else{
            node.setNext(this.head); //node.next = this.head;
            head.setPrev(node);//head.prev = node;
            this.head = node;
        }
    }
    /***
     * 2.尾插法——时间复杂度O(1)
     * @param data
     */
    public void addLast(int data){
        //(0)定义节点
        ListNode node = new ListNode(data);
        //(1)当链表为空
        if(this.head == null){
            this.head = node;
            this.last = node;
        }else{
            //（2）链表不为空
            this.last.setNext(node);//last.next = node;
            node.setPrev(last);//node.prev = last;
            this.last = node;
        }
    }

    /***
     * 3.在任意位置插入（第一个数据节点为0号下标）
     * @param index
     * @param data
     * @return
     */
    public void addIndex(int index,int data){
        //index的位置是否合法
        if(index < 0 || index > len()){
            return;
        }
        //头插法
        if(index == 0){
            addFirst(data);
            return;
        }
        //尾插法
        if(index == len()){
            addLast(data);
            return;
        }
        //(1) 找到index位置，修改前后指向
        ListNode cur = this.head;
        while(index != 0){
            cur = cur.getNext();//cur = cur.next;
            index--;
        }
        //(0)创建节点
        ListNode node = new ListNode(data);
        //（2）修改指针指向
        node.setNext(cur);//node.next = cur;
        node.setPrev(cur.getPrev());//node.prev = cur.prev;
        node.getPrev().setNext(node);//node.prev.next = node;
        cur.setPrev(node);//cur.prev = node;
    }

    /***
     * 4.查找是否包含关键字为key的节点
     * @param key
     * @return
     */
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur != null){
            if(cur.getVal() == key){
                return  true;
            }
            cur = cur.getNext();
        }
        return false;
    }

    /***
     * 5.删除第一次出现关键字key的节点
     * @param key
     */
    //方法1：
    public void remove1(int key){
        ListNode cur = findNode(key);
        if(cur == null){
            return;
        }
        //（1)删头节点
        if(cur == this.head){
            this.head = this.head.getNext();
            this.head.setPrev(null);
            return;
        }
        //(2)删尾节点
        if(cur == this.last){
            cur.getPrev().setNext(null);//cur.prev.next =null;
            this.last = this.last.getPrev();//this.last = this.last.prev;
            return;
        }
        //(3)删中间节点
        cur.getPrev().setNext(cur.getNext());
        cur.getNext().setPrev(cur.getPrev());
    }

    /***
     * 首先查找到要删除的元素
     * @param key
     * @return
     */
    public ListNode findNode(int key){
        if(this.head == null){
            return null;
        }
        ListNode cur = this.head;
        while(cur != null){
            if(cur.getVal() == key){
                return cur;
            }
            cur = cur.getNext();
        }
        return null;
    }
    //方法2：
    public void remove2(int key){
        ListNode cur= this.head;
        while(cur != null){
            if(cur.getVal() == key){
                if(cur == this.head){
                    //删除头结点
                    this.head = this.head.getNext();
                    this.head.setPrev(null);
                    return;
                }else{
                    //cur.prev.next = cur.next;
                    cur.getPrev().setNext(cur.getNext());
                    if(cur.getNext() != null){//考虑删尾结点
                        //cur.next.prev= cur.prev;
                        cur.getNext().setPrev(cur.getPrev());
                    }else{
                        //cur.next == null的情况
                        this.last = this.last.getPrev();
                    }
                    return;
                }
            }else{
                cur = cur.getNext();
            }
        }
    }

    //方法3：
    public void remove3(int key){
        ListNode cur= this.head;
        while(cur != null){
            if(cur.getVal() == key){
                if(cur == this.head){
                    //删除头结点
                    this.head = this.head.getNext();
                    this.head.setPrev(null);
                    return;
                }else if(cur == this.last) {//删尾节点
                    cur.getPrev().setNext(null);//cur.prev.next = null
                    this.last = this.last.getPrev();//this.last = this.last.prev;
                    return;
                }else{
                    //cur.prev.next = cur.next;
                    cur.getPrev().setNext(cur.getNext());
                    //cur.next.prev= cur.prev;
                    cur.getNext().setPrev(cur.getPrev());
                    return;
                }
            }else{
                cur = cur.getNext();
            }
        }
    }

    /***
     * 6.删除所有值为key的节点
     * @param key
     */
    public void removeAllKey(int key){
        ListNode cur= this.head;
        while(cur != null) {
            if (cur.getVal() == key) {
                if (cur == this.head) {
                    //删除头结点
                    this.head = this.head.getNext();
                    this.head.setPrev(null);
                } else if (cur == this.last) {//删尾节点
                    cur.getPrev().setNext(null);//cur.prev.next = null
                    this.last = this.last.getPrev();//this.last = this.last.prev;
                } else {
                    //cur.prev.next = cur.next;
                    cur.getPrev().setNext(cur.getNext());
                    //cur.next.prev= cur.prev;
                    cur.getNext().setPrev(cur.getPrev());
                }
            }
            cur = cur.getNext();
        }
    }
    /***
     * 7.获取链表的长度
     * @return
     */
    public int len(){
        int count= 0;
        ListNode cur = this.head;
        while(cur != null){
            count++;
            cur = cur.getNext(); //cur= cur.next;
        }
        return count;
    }

    /***
     * 8.打印链表
     */
    public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.getVal() + " ");
            cur = cur.getNext();//cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 9.清空链表
     */
    public  void clear1(){
        this.head.setPrev(null);//this.head = null;
        this.last.setPrev(null);//this.last = null
    }

    public  void clea2(){
        ListNode cur = this.head;
        while(cur != null){
            ListNode curNext = cur.getNext();
            cur.setNext(null);//cur.next = null;
            cur.setPrev(null);//cur.prev = null;
            cur = curNext;
        }
        this.head.setPrev(null);//this.head = null;
        this.last.setPrev(null);//this.last = null
    }
}
